package cn.lishiyuan.leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 给定n个二维平面上的点，求一组欧几里得距离最近的点对。
 */
public class NearPoint {

    public static record Point(int x, int y) {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static double distance(Point p1, Point p2){
        return Math.sqrt(Math.pow(p2.x-p1.x,2) + Math.pow(p2.y-p1.y,2));
    }

    /**
     * 循环计算
     * @param points
     * @return
     */
    public static Point[] resolveCycle(List<Point> points) {
        double distance = Double.MAX_VALUE;
        Point[] result = new Point[2];

        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                // 计算距离
                Point p1 = points.get(i);
                Point p2 = points.get(j);
                double d = distance(p1, p2);
                if (d < distance) {
                    distance = d;
                    result[0] = p1;
                    result[1] = p2;
                }
            }
        }
        return result;
    }


    /**
     * 分治解决
     * @param points
     * @return
     */
    public static Point[] resolveDAC(List<Point> points) {
        // X坐标排序
        points.sort(Comparator.comparing(point -> point.x));
        // 分割成左右两部分

        return dac(points,0,points.size() - 1);
    }

    private static Point[] dac(List<Point> points , int start, int end){
        if(start >= end) return null;
        int mid = start + (end-start) / 2;

        Point[] result = null;
        Point[] left = dac(points,start,mid);
        Point[] right = dac(points,mid+1,end);

        // 计算最短距离
        double distance = -1;
        if(left != null && right != null){
            double distanceL = distance(left[0],left[1]);
            double distanceR = distance(right[0],right[1]);
            if(distanceL < distanceR){
                distance = distanceL;
                result = left;
            }else {
                distance = distanceR;
                result = right;
            }
        }else {
            if(left != null){
                distance = distance(left[0],left[1]);
                result = left;
            }else if(right != null){
                distance = distance(right[0],right[1]);
                result = right;
            }
        }

        // 合并
        Point[] merge = merge(points,start,mid,end,distance);

        // 如果交集部分正好小于距离
        if(merge != null){
            double distanceM = distance(merge[0],merge[1]);
            if(distanceM < distance){
                result = merge;
            }
        }

        return result;
    }


    private static Point[] merge(List<Point> points,int start,int mid,int end, double distance){
        // distance划正方形
        if(start >= end) return null;
        List<Point> sub = new ArrayList<>();

        if(distance == -1){
            // 全部内容
            sub = points.subList(start,end+1);
        }else {
            int left = mid;
            int right = mid;
            Point midP = points.get(mid);

            for (;left > start;left--){
                Point point = points.get(left);
                int abs = Math.abs(point.x - midP.x);
                if(abs <= distance){
                    break;
                }
            }

            for (;right < end;right++){
                Point point = points.get(right);
                int abs = Math.abs(point.x - midP.x);
                if(abs <= distance){
                    break;
                }
            }

            sub = points.subList(left,right+1);

            // 再按照排序，再处理
            sub.sort(Comparator.comparing(point -> point.y));


        }

        return null;
    }





}
